﻿static List<int> sort(List<int> lst)
{
    if (lst.Count <= 1)
        return lst;
    int mid = lst.Count / 2;
    List<int> left = new List<int>();  // 定义左侧List
    List<int> right = new List<int>(); // 定义右侧List
    // 分成左右两个
    for (int i = 0; i < mid; i++)
        left.Add(lst[i]);
    for (int j = mid; j < lst.Count; j++)
        right.Add(lst[j]);
    left = sort(left);
    right = sort(right);
    return merge(left, right);
}
/// <summary>
/// 合并两个排好的list
/// </summary>
/// <param name="left">左侧</param>
/// <param name="right">右侧</param>
/// <returns></returns>
static List<int> merge(List<int> left, List<int> right)
{
    List<int> temp = new List<int>();
    while (left.Count > 0 && right.Count > 0)//左右连个都有值
    {
        //将小的放入到 临时数列中
        //并移除 对应值
        if (left[0] <= right[0])//左侧第一个小于右侧第一个
        {
            temp.Add(left[0]);
            left.RemoveAt(0);//
        }
        else
        {
            temp.Add(right[0]);
            right.RemoveAt(0);
        }
    }
    //将左侧剩余的放入到临时数列中
    if (left.Count > 0)
    {
        for (int i = 0; i < left.Count; i++)
            temp.Add(left[i]);
    }
    //将右侧剩余的放入到临时数列中
    if (right.Count > 0)
    {
        for (int i = 0; i < right.Count; i++)
            temp.Add(right[i]);
    }
    Show(temp);
    return temp;
}
/// <summary>
/// 显示
/// </summary>
static void Show(List<int> lst)
{
    foreach (int i in lst)
        Console.Write(i + " ");
    Console.WriteLine();
}

List<int> lst = new List<int> { 5, 2, 4, 3, 1 };
lst = sort(lst);
Show(lst); 